\section{Proof and contradiction}
\begin{enumerate}
	\item
		\begin{enumerate}
			\item A proof by contradiction means that the original theorem will be assumed false and hence a contradiction will be derived. If it is possible to derive a contradiction, than the assumption that the theorem is false cannot be true, so in that case this is a proof that the original theorem must be true.
			
			A proof by contraposition means that the antecedent and consequent both are switched and logically inverted. In logic, if the original theorem is $ p \rightarrow q $, the theorem to be proven by contraposition is $ \neg q \rightarrow \neg p$. A proof by contraposition is only possible if the theorem to be proven is an implication.
			
			The main difference is that in a proof by contradiction you are looking for a counterexample, which that you don't do in a proof by contraposition.
			\item  
				\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
				\item  
					 \begin{theorem} 
						Assume $x$ is odd. Then $x$ equals the difference of two square numbers.
					\end{theorem} 
					
					
					Odd numbers: $ 2n+1 (n \in \mathbb{N})	\rightarrow \{1,3,5,7,9,\ldots\}$
					
					Square numbers: $n^2 (n \in \mathbb{N}) \rightarrow 	\{0,1,4,9,16,25,\ldots\}$
					
					Hence it is noticeable that all odd numbers equal the difference of the two following square numbers.
					
					\begin{corollary} 
						Assume $x$ is odd. Then $x$ equals the difference of the two following square numbers.
					\end{corollary} 
					
					\begin{proof}\
						\begin{align*}
						 x & = (K+1)^2-K^2 	\\
						 x & = K^2+2K+1-K^2 \\
						 x & = 2K+1 \rightarrow odd
						\end{align*}
						
						The corollary is true. Hence, the original theorem is also true.
					
					\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
					\item   
						\begin{theorem} 
								Assume $ a|b $ and $ a|b+c $. Then $ a|c $.
					 	\end{theorem}
						\begin{proof}\
								\begin{align*}
								 	\frac{b}{a} 	& = k (k \in \mathbb{N})	\\
								  \frac{b+c}{a} & = k (k \in \mathbb{N}) \\
								   \frac{b}{a} + \frac{c}{a} & = k_1 + k_2 (k \in \mathbb{N})
								\end{align*}
						
						Because $ a|b \in \mathbb{N} $ and $ (k_1 + k_2) \in \mathbb{N} $, then  $ k_2 \in \mathbb{N} $ because the collection of natural number is closed under addition, subtraction and multiplication. This implicates that $ a|c $ because $ k $ exists in $ c=ak $ with $ k \in \mathbb{N} $.
						
						\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
				\item   
						\begin{theorem} 
								Assume $ a|b $ and $ a|bc $. Then $ a|c $.
					 	\end{theorem}
						
									$ a|b $ means that there exists a number $ k \in \mathbb{N} $ that $ b=ka $. \\ E.g. $ a=2$ and $ b=10 $, then $ k = 5 $.									\\\\
									$ a|bc $ means that there exists a number $ k \in \mathbb{N} $ that $ bc=ka $. \\ E.g. $ a=2, b=10 $ and $ c=5 $, then $ k = 25 $.					\\\\
									Now take $ a=2$, $ b=1 $ and $ c=5 $. For $a|c$, this means that $bc=ka$ with $k \in \mathbb{N}$. This results in $5=2k$ which implicates that $k= 2,5 \notin \mathbb{N} $, and this is not a natural number. Counterexample!		
									\\
									So the theorem is not correct.					
					
			\end{enumerate}
			\item 
					\begin{theorem} 
							Assume that $ x $ is a four-digits palindromenumber. Then $ 11|x $.
				 	\end{theorem}
					\begin{proof}\
						The number $x$ can be written as $ abba $, where all four letters represent a digit. $a \in \{1,2,\ldots,9\}$ and $b \in \{0,1,\ldots,9\}$.
						
						\begin{align*}
							abba 	& =1000a+100b+10b+a        \\
							     	& =1001a+110b  						\\
		\frac{abba}{11} & = \frac{1001a+110b}{11} \\
										& =\frac{1001}{11} a+ \frac{110}{11}b \\
										& =91a+10b  \\
						\end{align*}
						Integers are closed under addition, subtraction and multiplication. This means that the outcome of $91a+10b$ must be a integer if $a$ and $b$ are integers. As $a$ and $b$ are integers, the outcome must be an integer.
						
					\end{proof}
			
	\end{enumerate}
\end{enumerate}

\section{Induction}
	\begin{enumerate}
				\item[a] 
					\begin{theorem}
						For all the natural numbers $n\geq1$ than: \\
						$ \sum_{i=1}^{n}i^3=\frac{1}{4}n^2(n+1)^2 $ \\					
					\end{theorem}
					
					\begin{proof}\
						\begin{description}
						\item[Base step] $n=1$	\\
						$ \sum_{i=1}^{1}i^3=1^3=1=\frac{1}{4}1^2(1+1)^2=\frac{1}{4}n^2(n+1)^2 $	\\
						\item[Induction step] for all $n\geq 1$	\\
						$ P(n)\rightarrow P(n+1)$ \\
						For $k\geq1$ random $ P(k)$	\\
						$ \sum_{i=1}^{k}i^3=\frac{1}{4}k^2(k+1)^2 $ \\
						
						To be proven: $P(k+1)=\sum_{i=1}^{k+1}i^3=\frac{1}{4}(k+1)^2(k+2)^2 $ \\
						\begin{align*}
							\sum_{i=1}^{k+1}i^3&=\sum_{i=1}^{k}i^3+(k+1)^3 \\
																IH&=\frac{1}{4}k^2(k+1)^2+(k+1)^3 \\
																	&=\frac{1}{4}k^2(k^2+2k+1)+(k^3+3k^2+3k+1) \\
																	&=\frac{1}{4}k^4+\frac{6}{4}k^3+\frac{13}{4}k^2+3k+1 \\
																	&=\frac{1}{4}(k^4+6k^3+13k^2+12k+4) \\
																	&=\frac{1}{4}(k^2+2k+1)(k^2+4k+4) \\
																	&=\frac{1}{4}(k+1)^2(k+2)^2 \\
						\end{align*}
						\end{description}
						Because $k$ was choosen randomly, the following is true for all $n\geq1$: $P(n)\rightarrow P(n+1)$ \\
						Following the principle of induction $P(n)$ is true for $n\geq1 $\\
					\end{proof}
					
					
			
					
					\item[b]
					\begin{theorem}
						In all groups of horses of size $n\geq 1$ all horses have to same color. In other words, all horses have te same color.
					\end{theorem}
					
					The proof by induction provided in this exercise contains an error.
					\\
					The proof stated that if the horses in the set $\{h_1, h_2, \ldots , h_n \}$ are all of the same color, then all horses in the set $\{h_2, h_3, \ldots , h_{n+1} \}$ have the same color as well. But this is an incorrect claim! The problem is, that at first sight it looks like both sets overlap, but this is not te case when $n=1$. If $n=1$, the first set is $\{h_1 \}$ and the second set is $\{h_2 \}$, and they do not overlap at all!
					\\\\
					To summarize, $P(1)$ is proven, and $P(2)\Rightarrow P(3), P(3)\Rightarrow P(4) ,\ldots $ is proven, but what is missing is the proof for  $P(1)\Rightarrow P(2)$.
					\\\\
					Conclusion: This proof is incorrect, and so is the claim, and in matter of fact, ofcourse there are horses with a different color.
					\item[c]
					
						\begin{enumerate}
							\item[i]
								% moet nog evne vertaalt worden
								Define (The function $P:PROP\mapsto \mathbb{N}$ for the numner of proposition symbols)
								
								Recursive definition	\\
								\begin{align*}
									P(p_{i})&=1							&\text{For every } p_i\in PROP		\\
									P(\neg A)&=P(A)					&\text{For every } A\in PROP			\\
									P((A\ast B))&=P(A)+P(B)	&\text{For every } A\in PROP			\\
								\end{align*}
								
							\item[ii]
								Define (The function $t:PROP\mapsto \mathbb{N}$ for the number of the binair connectives)\\
								
								Recursive definition\\
								\begin{align*}
									t(p_{i})		&=0								&\text{For every } p_i\in PROP		\\
									t(\neg A)		&=t(A)						&\text{For every } A\in PROP			\\
									t((A\ast B))&=t(A)+t(B)+1			&\text{For every } A\in PROP			\\
								\end{align*}
								
							\item[iii]			
							Proof with structural induction over $PROP$ that the follwoing theorem is true\\
							Theorem for every formula $F\in PROP$, the following is true $P(F)=t(F)+1$ \\
							\begin{proof}\
								\begin{description}
								\item[Base step] $P(F)=t(p_{i})+1$ geldt voor $F=p_{i} (i\in \mathbb{N})$	\\

								\begin{align*}
										P(p_i) 	&= 1+t(p_i)	\\
												1 	&= 1+0						\\
												1		&= 1	\text{ is equal }	\\
								\end{align*}
								
								\item[Induction step]
								Suppose $P(F)$ equals for $F=A,B\in PROP (IH)$
								To be proven $P(F)$ for: $F=\neg A$ and $F=(A\ast B)$
								
								$F=\neg A$
							
								\begin{align*}
									P(\neg A)	&=	t(\neg A)+1	\\
									P(A)			&=	t(A)+1				\\
								\end{align*}
								Is equal according to the induction hypothesis.
								
								$F=(A\ast B)$ \\
								\begin{align*}
											F=((A\ast B))	 	&= t((A\ast B))+1		\\
											P(A)+P(B) 			&= t(A)+t(B)+1+1		\\
											t(A)+1+t(B)+1 	&= t(A)+t(B)+2	(IH)\\
											t(A)+t(B)+2 		&= t(A)+t(B)+2			\\
								\end{align*}
								
								Is also equal according to the induction hypothesis.
								\end{description}
							\end{proof}
						\end{enumerate}
					
					
					
\end{enumerate}

\section{Truthness tables}
	\begin{enumerate}
				\item[a] 	
					
						\textbf{Reasoning definition}\\
						\begin{tabular}{lcl}
						 		premiss 1&:&	The earth is flat or rounded	\\
						 		
						  	premiss 2&:& If Beatrix is the queen of Belgium, then the earth is flat \\
						  	premiss 3&:& Beatrix is the queen of Belgium  \\
						  	conclusion&: & The earth is not round \\
						\end{tabular}
						
						\textbf{Symbol definitions}\\
						\begin{tabular}{ll}
								b &	= ``Beatrix is the queen of Belgium"	\\
						 		f &	= ``The earth is flat"	\\
						 		r &	= ``The earth is rounded"	\\
						\end{tabular}
						
						\textbf{Reasoning noted with symbols}\\
						\begin{tabular}{l}
							$ f \vee r $\\
							$ b \rightarrow f $ \\
							$ b $  \\
							\hline
							$\therefore \neg r $ \\
						\end{tabular}
						
						\textbf{Truthness table}\\
							\begin{tabular}{|c|c|c||c|c|c||c||c|}
							\hline
							$b$ & $f$ & $r$ & $ f \vee r $  & $ b \rightarrow f $ & $b$ &  $ \therefore $ 	& $\neg r$  \\
							\hline
							\hline
							0 & 0 	& 0 	&			0							& 					1					&		0 &								 	&		1		\\
							0 & 0 	& 1 	&			1							& 					1					&		0	&		 							&		0		\\
							0 & 1 	& 0 	&			1							& 					1					&		0	&		 							&		1		\\
							0 & 1 	& 1 	&			1							& 					1					&		0	&		 							&		0		\\	
							1 & 0 	& 0 	&			0							& 					0					&		1 &								 	&		1		\\
							1 & 0 	& 1 	&			1							& 					0					&		1	&		 							&		0		\\
							1 & 1 	& 0 	&			1							& 					1					&		1	&	*	 							&		1		\\
							\hline
							1 & 1 	& 1 	&			1							& 					1					&		1	&	\textbf{*}			&		0 	\\	
							\hline
						\end{tabular}	\\
						The reasoning is wrong because in the bottom line of the truthness table the premisses are all true but the conclusion is false.
						
						Therefore the reasoning $ (f \vee r) \wedge (b \rightarrow f)  \wedge b \therefore \neg r$ is logically not correct. A counterexample is: $b = 1, f = 1, r =1 $. All the premisses are true but the conclusion is false.
						
					\item[b]  The difference between the natural language and the language of proposition logic, is that proposition logic is solely about the structure of an argument, and not about the meaning of the premisses.
					\item[c]
						 		The premiss that have to be added is: ``\textit{Beatrix is the queen of Belgium, the earth is flat and the earth is not round}".
						 		
						 		The new schema becomes:
							\begin{tabular}{l}
								$ f \vee r $\\
								$ b \rightarrow f $ \\
								$ b $  \\
								$ b \wedge f \wedge \neg r $  \\
								\hline
								$\therefore \neg r $ \\
							\end{tabular}	
						 	
						 	Hence the antecedent becomes  $ (f \vee r) \wedge (b \rightarrow f)  \wedge b \wedge b \wedge f \wedge \neg r $. Due to the added premiss the antecedent becomes false for the provided counterexample ($b = 1, f = 1, r = 1$) and thus with the added premiss the reasoning becomes valid.
						 		
\end{enumerate}


\section{Meta-definitions}
	\begin{enumerate}
				\item[a]
						To prove: $ \models \neg A \rightarrow \neg B \therefore \models  A \vee \neg B$
						
						\begin{proof}\
						Suppose  $ \models \neg A \rightarrow \neg B $. All valuations are a model for $ \neg A \rightarrow \neg B $, 
						so for every valuation the following is true $ v(\neg A \rightarrow \neg B)=1 $.\\
						
						\begin{align*}
							v(\neg A \rightarrow \neg B) &= max(1-v(\neg A), v(\neg B)) 		&=1		\\
																					&= max(1-(1-v( A)), 1-v(B))					&=1		\\
																					&= max(v( A), 1-v(B))								&=1		\\
						\end{align*}
						This means that $ v(A)=1 $ or $ v(B)=0 $ is true for all valuations. \\
						
						We take a random valuation $w$ for which the following is also true $ v(A)=1 $ or $ v(B)=0 $. \\
						\begin{align*}
							w(A \vee \neg B) &= max(v(A),v(\neg B)) &= 1	\\
																&= max(v(A),1-v(B)) &= 1		\\
						\end{align*}
						
						When we fill in $ v(A)=1 $ or $ v(B)=0 $, $ max(1,1-w(B)) = 1 $ and $ max(w(A),1-0) = 1 $. 
						For this random valuation $v$ that is a model for $ \neg A \rightarrow \neg B $ the following is true $ v(\neg A \rightarrow \neg B) = 1 $ 
						
						\end{proof}
						
					\item [b]
						To prove: If $ \models \neg A \rightarrow \neg B $ than $ \models A \bigvee \models \neg B $.
						
						\begin{proof}\
						Suppose $ \models \neg A \rightarrow \neg B $ Alle valuation are a model for $ \neg A \rightarrow \neg B $. so that for all valuation $v$ the following is true, $v(\neg A \rightarrow \neg B) = 1$. \\
						\begin{align*}
							v(\neg A \rightarrow \neg B) &= max(1-v(\neg A),v(\neg B))&=1		\\
																					&= max(1-(1-v(A)),1-v(B))		&=1			\\
																					&= max(v(A),1-v(B))					&=1			\\
						\end{align*}
						For every valuation of $ \models \neg A \rightarrow \neg B $ the follwoing is true $ v(A)=1 $ or $v(B)=0 $.
						
						
						We take a random valuation $w$ for which the follwoing is also true $ v(A)=1 $ or $v(B)=0 $. For the random valuation $w(A)=1$ or $w(\neg B)=1-w(B)=0$ $w(B)=0$. As we selected $w$ random it is a model for every valenties of $ \models \neg A \rightarrow \neg B $ also a model for $ \models A \bigvee \models \neg B $.
						
						\end{proof}
					
					\item [c]
						To prove: If $ \models \neg A $ than $ \sim \models A $. \\
						
						\begin{proof}
						
						Suppose $ \models \neg A $ is true, that means that $ v(\neg A)=1-v(A)=1 $ and thus $v(A)=0$. 
						$ \sim \models A$ means that $A$ is not a tautology. If we take a random valuation for which the following $w(A)=0$ is true as well, and fill this in we get $w(A)=0$ and as $A$ was not a tautology this is true. 
						
						\end{proof}
						
					\item [d]
						To prove wrong: If $\sim \models A$ than $\models \neg A$.
						
						If we asume that $\sim \models A$ is true, that means that the valuation $v$ of $v(A)=0 \bigvee v(A)=1$, all we truly know is that its not always 1. For the random valuation of $w$  we asume two cases:\\
											
					\begin{enumerate}
						\item $w(A)=0$ for all the potential variations of $A$, that means that $v( \neg A ) = 1-v(A) = 1$ and its a tautology.
						\item $w(A)=1 $ for all the potential variantions of $A$, that means that $v( \neg A ) = 1-v(A) = w(A)=0$. 
	
					\end{enumerate}
						
						
						
						
						The last case is not a tautology and thus $\sim \models A $ is not equal to $\models \neg A $ for all the variations v(A).
						
						
						
																				
	\end{enumerate}